package jago02.jago0201.ag02_lineTable;

import java.util.Iterator;

/**
 * 链式队列
 * 杂化简：链式队列从首节点head开始一直往后追加节点元素，节点存储元素和下一个节点,尾节点last存储最后一个元素
 *
 * 解目录：
 *      1.用N表示链式队列长度，表示链式队列的元素个数
 *      2.内部类Node包含元素值、下个节点
 *      3.入队列就是新增数据节点，并追加到老尾节点后，新节点变成尾节点，老尾节点的next指向新节点，N++
 *      4.出就是每次都移除首节点后的第一个节点，即head.next的位置，然后head.next指向被移除节点的next,N--，后再次判空，如果为空则设置尾节点last为空
 * 复杂度：入队列方法是O(N)，出队列方法是O(1)
 */
public class LineTable05_Queue<T> implements Iterable<T> {
    //节点内部类
    private class Node{
        T item;
        Node next;
        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    //头节点
    private Node head;
    //尾节点
    private Node last;
    //链式队列长度
    private int N;
    //构造
    public LineTable05_Queue() {
        this.head = new Node(null,null);
        this.last = null;
        this.N = 0;
    }
    //链式队列判空
    public boolean isEmpty(){
        return this.N == 0;
    }
    //获取链式队列长度
    public int size(){
        return this.N;
    }

    //入队列
    public void enqueue(T t){
        if (this.last == null){
            this.last = new Node(t,null);
            this.head.next = this.last;
        }else{
            //当尾节点不为null
            Node oldLast = this.last;
            this.last = new Node(t,null);
            oldLast.next = this.last;
        }
        this.N++;
    }
    //出队列
    public T dequeue(){
        if (isEmpty()){
            return null;
        }
        Node oldFirst = head.next;
        head.next = oldFirst.next;
        N--;
        //出队列后再次判空
        if (isEmpty()){
            last = null;
        }
        return oldFirst.item;
    }


    private class QueueListIterator implements Iterator{
        private Node curr;

        public QueueListIterator() {
            this.curr = head;
        }

        @Override
        public boolean hasNext() {
            return this.curr.next != null;
        }
        @Override
        public Object next() {
            curr = curr.next;
            return curr.item;
        }
    }

    @Override
    public Iterator iterator() {
        return new QueueListIterator();
    }

    public static void main(String[] args) {
        LineTable05_Queue<String> queue = new LineTable05_Queue();

        queue.enqueue("张三");
        queue.enqueue("李四");
        queue.enqueue("王五");
        queue.enqueue("老朱");
        System.out.println(queue);
        for (String str : queue) {
            System.out.print(queue.dequeue()+" ");
        }
    }
}
